package 动态规划;

/**
 * 97. 交错字符串
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 *
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
 * 子字符串
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 注意：a + b 意味着字符串 a 和 b 连接。
 *
 * 解题思路：
 *  1：基本的判断条件：
 *      如果s3的长度不等于s1和s2的长度之和，则直接返回false
 *      如果s1或s2是空字符串，则检查另一个字符串是否等于s3
 *  2：动态规划的定义：
 *      用一个二维数组dp[i][j]表示：
 *          dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前i+j个字符。
 *  3：状态转移方程：
 *      如果 s3[i + j - 1] == s1[i - 1]，即第x个字符时第一个字符串中的，则可以从 dp[i-1][j] 转移过来
 *      如果s3[i + j - 1] == s2[j - 1]， 即第x个字符是第二个字符串中的，则可以从dp[i][j-1] 转移过来
 *     因此转移方程为：
 *      dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
 *  4. 边界条件
 *      dp[0][0] = true，表示两个空字符串可以交错组成一个空字符串。
 *      初始化第一行和第一列：
 *      第一行：只使用 s2 的字符匹配 s3。
 *      第一列：只使用 s1 的字符匹配 s3。
 *  5. 返回结果
 *      最终结果存储在 dp[s1.length()][s2.length()] 中。
 */
public class L_97 {

    public boolean isInterleave(String s1, String s2, String s3) {
        // 检查字符串长度是否够满足条件
        if(s1.length() + s2.length() != s3.length()){
            return false;
        }
        int m = s1.length();
        int n = s2.length();
        // 创建dp数组
        boolean[][] dp =new boolean[m+1][n+1];

        // 初始化边界条件
        dp[0][0] = true;
        // 初始化第一列
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
        }
        // 初始化第一行
        for (int j = 1; j <=n ; j++) {
            dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
        }
        // 状态转移方程--填充dp数组
        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                dp[i][j] = ( dp[i-1][j] && s3.charAt(i+j-1) == s1.charAt(i-1) )
                        ||  ( dp[i][j-1] && s3.charAt(i+j-1) == s2.charAt(j-1));
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        L_97 l_97 = new L_97();
        String s1 = "aabcc";
        String s2 = "dbbca";
        String s3 = "aadbbcbcac";

        System.out.println(l_97.isInterleave(s1, s2, s3)); // 输出: true
    }
}
